// 基础 

const arr = [3, 4, 1, 2, 0];
// const arr = [0, 1, 2, 3, 4];

// 基础版本 O(n^2)
// for (let i = 0; i < arr.length; i++) {
//   for (let j = 0; j < arr.length - 1; j++) {
//     if (arr[j] > arr[j + 1]) {
//       //   const temp = arr[j];
//       //   const temp1 = arr[j+1];
//       //   arr[j+1] = temp
//       //   arr[j] = temp1
//       [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
//     }
//   }
// }

// // 优化 O(n^2)
// for (let i = 0; i < arr.length; i++) {
//   for (let j = 0; j < arr.length - i; j++) {
//     if (arr[j] > arr[j + 1]) {
//       [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
//     }
//   }
// }

// 最好情况 O(n) 即当arr为0, 1, 2, 3, 4 时
let flag = false;
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length - i; j++) {
    if (arr[j] > arr[j + 1]) {
      flag = true;
      [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
  }
  if (!flag) {
    break;
  }
}

console.log(arr);
